#字典树节点
class Node:
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

class Trie:

    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            # 将当前字符添加到当前节点对应的子节点位置，然后递归更新
            id_ = ord(char) - ord('a') #这行代码的作用是 将一个字母 char 转换成一个 0 开始的索引值
            if not node.children[id_]:
                node.children[id_] = Node()
            node = node.children[id_]
        node.isEnd = True # 最后一个节点的isEnd置为true，表示一个完整的字符串

    def search(self, word: str) -> bool:
        node = self.__search_prefix(word)
        return node != None and node.isEnd # 返回不为空且节点标记为尾节点，则包含word这个完整的字符串

    def startsWith(self, prefix: str) -> bool:
        return self.__search_prefix(prefix) != None # 返回不为空，则包含了prefix前缀

    #查找字典树是否包含word前缀
    def __search_prefix(self, word:str) -> Node:
        node = self.root  # 从根节点依次开始匹配每个字符
        for char in word:
            node = node.children[ord(char) - ord('a')]
            if not node:
                return
        return node



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)